Embodiments of the present invention relate to the field of electronic design automation (EDA). More particularly, embodiments of the present invention relate to techniques for cell placement and other optimizations used in the design and fabrication of integrated circuit devices.
An electronic design automation (EDA) system is a computer software system used for designing integrated circuit (IC) devices. The EDA system typically receives one or more high level behavioral descriptions of an IC device (e.g., in HDL languages like VHDL, Verilog, etc.), as represented by HDL 12 of FIG. 1, and translates this high level design language description into netlists of various levels of abstraction. At a higher level of abstraction, a generic netlist is typically produced based on technology independent primitives. The generic netlist can be translated into a lower level technology-specific netlist based on a technology-specific library that has gate-specific models for timing and power estimation. A netlist describes the IC design and is composed of nodes (elements) and edges, e.g., connections between nodes, and can be represented using a directed cyclic graph structure having nodes which are connected to each other with signal lines. A single node can have multiple fan-ins and multiple fan-outs.
The netlist is typically stored in computer readable media within the EDA system and processed and verified using many well known techniques. One result is a physical device layout in mask form which can be used to directly implement structures in silicon to realize the physical IC device, step 28 of FIG. 1.
The rapid growth of the complexity of modern electronic circuits has forced electronic circuit designers to rely upon computer programs to assist or automate most steps of the design process. Typical circuits today contain hundreds of thousands or millions of individual pieces or xe2x80x9ccells.xe2x80x9d Such a design is much too large for a circuit designer or even an engineering team of designers to manage effectively manually.
FIG. 1 shows a typical system 10 of computer programs and other processes used to automate the design of electronic circuits. Within system 10, the designer first produces a high-level description 12 of the circuit in a hardware description language such as Verilog or VHDL. Then this high-level description 12 is converted into a netlist 16a using a computer implemented synthesis process 14 such as the xe2x80x9cDesign Compilerxe2x80x9d by Synopsys of Mountain View, Calif. A netlist 16a is a description of the electronic circuit which specifies what cells compose the circuit and which pins of which cells are to be connected together using wires (xe2x80x9cnetsxe2x80x9d). Importantly, the netlist 16a does not specify where on a circuit board or silicon chip the cells are placed or where the wires run which connect them together. Determining this geometric information is the function of an automatic placement process 18 and an automatic routing process 22, both of which are shown in FIG. 1 and are typically computer programs.
Next, the designer supplies the netlist 16a into the computer implemented automatic cell placement process 18 of FIG. 1. The automatic placement computer program 18 finds a location for each cell on a circuit board or silicon chip. The locations are specified, typically, in two-dimensional spatial coordinates, e.g., (x, y) coordinates, on the circuit board or silicon chip. The locations are typically selected to optimize certain objectives such as wire length, wire routibility, circuit speed, circuit power consumption, and/or other criteria, subject to the condition that the cells are spread evenly over the circuit board or silicon chip and that the cells do not overlap with each other. The output of the automatic cell placement process 18 includes a data structure 20 including the (x, y) position for each cell of the IC design. In some cases, the netlist 16a is modified and a new netlist 16b is generated. In other cases, the netlist 16b is the same as netlist 16a. 
Next, the designer supplies the netlist 16a and the cell location data structure 20, generated by the placement program 18, to a computer implemented automatic wire routing process 22.
Unfortunately, when dealing with hundreds of thousands or millions of cells, each cell typically having several interconnecting wires, even the best placements frequently can not be wired (step 22 of FIG. 1) due to congestion. Quite simply, there may be more wires which need to routed through particular areas of an integrated circuit than can be accommodated by the available places to route such wires.
If the design can not be wired by process 22, one well known technique which may be employed is optional process enlarge cell area allocation for congestion relief 23. In this process, the area allocated to cells in the region(s) of congestion is increased. The size of the cells is not increased, just the area allocated to the cells. This leaves room for routing wires within the apparent cell, which has the effect of creating more room for routing wires once the cells are placed, thus relieving congestion.
If the cell area allocations are optionally enlarged, the new cell area allocations are incorporated into the netlist database 16A and the layout process is repeated, beginning with computer implemented automatic cell placement process 18.
It would be desirable to resynthesize the design, that is, to continue the process flow through automatic post-layout synthesis optimizations 26 (or repeating computer implemented synthesis process 14) and then repeating cell placement process 18 with the xe2x80x9cenlargedxe2x80x9d cells. In theory, a new synthesis should help to further optimize the design. Unfortunately, however, in the prior art practice, multiple passes of automatic post-layout synthesis optmizations 26 (or computer implemented synthesis process 14) and placement 18 generally degrade the placement, leading to greater timing problems. It is believed that this behavior results from non-convergence of the two processesxe2x80x94synthesis 14 tries to optimize timing (in a non-placed form) while placement 18 tries to optimize wire length. These two goals may be in conflict.
If computer program 22 completes routing all wires, it may generate wire geometry within data structure 24. The wire geometry data structure 24 and cell placement data structure 20 together represent the details of the final circuit implementation.
As a check of the circuit implementation, the timing of the implementation is typically analyzed in optional automatic post-layout synthesis optimizations 26 and compared to the requirements of the design. For example, the designer may determine if the required minimum clock speed has been achieved. There are a variety of well known techniques and EDA tools to accomplish this task.
It is not uncommon for the results of analysis 26 to indicate some failures to meet required circuit timings, especially the first time through. If there are failures, an automatic synthesis pass makes modifications directly to the netlist.
Such adjustments are usually minor, such as changing the current-handling capacity of a circuit element in order to make its output signal travel faster to another circuit. Another common adjustment is to add a buffer cell, which may be used to speed signal propagation through the integrated circuit.
The modified circuit design 12 is then taken through an incremental (detailed) placement process 27 to legalize the added cells (i.e., to find spaces for the new cells). If automatic post-layout synthesis optimizations 26 indicates that all timings meet requirements, the circuit implementation is ready for fabrication 28. Of course, the analysis may indicate the need for further changes, additional passes through automatic post-layout synthesis optimizations 26 and incremental placement and legalization 27.
Still referring to FIG. 1, a well known, commonly used algorithm for placement process 18 is known as a quadratic-partition algorithm.
This prior art process is based on the observation that the problem of placing cells to minimize sum-of-squared wire lengths can be solved quickly and exactly for large problems using standard techniques. Partitioning is used to guarantee that the cells are spread evenly across the silicon chip or circuit board.
In the quadratic portioning process all cells start out in a rectangle which is the entire silicon chip or circuit board. This rectangle is partitioned into 2 rectangles. Each of these 2 rectangles gets partitioned into 2 rectangles, etc., until each rectangle contains a small number of cells (e.g., 20 cells). Usually, the process alternates between vertical and horizontal partition lines for each iteration of the main loop.
Quadratic partitioning placement runs relatively quickly on large circuits but its formulation is very inflexible. It can only optimize weighted sum-of-squared wire length. However, this metric is really the wrong objective. Namely, what is important in cell placement is wire routibility, circuit timing, power consumption, etc. Quadratic wire length is a poor approximation for these metrics. It is possible to approximate these metrics somewhat better by changing wire weights to emphasize wires that seem to be more important to make short. For example, wires on the critical timing path can have higher weight in order to improve the timing of the critical path. However, this second approach is still a poor approximation to the true objective function that placement should optimize. Also, the selection of the position of the partition line location is arbitrary and unfortunately can introduce non-optimal artifacts in the placement along the partition lines.
A more effective placement process is described in U.S. patent application Ser. No. 09/216,632 filed on Dec. 16, 1998, xe2x80x9cNon-linear Optimization System and Method for Wire Length and Delay Optimization for an Automatic Electronic Circuit Placer,xe2x80x9d hereinafter referred to as the technique of direct timing driven placement.
Direct timing driven placement uses general unconstrained non-linear optimization techniques to find a coarse placement of cells on a circuit board or silicon chip. A master objective function (MOF) is defined which evaluates the quality of a particular cell placement. In effect, the MOF measures the xe2x80x9cgoodnessxe2x80x9d of the particular cell placement. A non-linear optimization process finds an assignment of values to the function variables which minimizes the MOF. The MOF is chosen so that values of variables which minimize the MOF correspond to a good coarse placement.
In particular, the MOF is a weighted sum of functions which evaluate various metrics. An important metric taken into consideration within the MOF is the density function which measures how well spread out the cells are in the placement.
Other component functions of the MOF are a wire-length function which measures total linear wire-length, a delay function which measures circuit timing, and a power function which measures circuit power consumption. The barrier metric or xe2x80x9cboundary function,xe2x80x9d penalizes placements with cells outside the allowed placement region.
Unfortunately, when computer implemented automatic cell placement process 18 is implemented using direct timing driven placement, the placement results are generally unsatisfactory.
This rather surprising result stems from the simultaneous optimization of timing while placing cells within the direct timing driven placement process. Direct timing driven placement attempts to optimize timing at the instantaneous moment of placement. Unfortunately, direct timing driven placement does not know what the timing will be after automatic post-layout synthesis and legalization 27. This lack of future knowledge may drive direct timing driven placement to make improper optimizations.
As an unfortunate consequence, the many potential benefits of direct timing driven placement have not been realized in the prior art. Thus, integrated circuits are larger, more costly, run slower and require more time and engineering effort to design.
Therefore, it would be advantageous to provide a method and system that enables the optimizations of direct timing driven placement of electronic circuits. A further need exists to resynthesize a circuit description after cell areas have been enlarged for congestion relief. A still further need exists for multiple pass optimization of the physical design of an integrated circuit.
Embodiments of the present invention enable the use of direct timing driven placement of electronic circuits. Further embodiments of the present invention allow a circuit design to be resynthesized after the design has been placed. Still further embodiments of the present invention enable optimization of the physical design of an integrated circuit through multiple passes of the physical design process.
A computer implemented process for the automatic creation of integrated circuit (IC) geometry is disclosed. In particular, the present invention includes a multiple pass process flow which uses multiple passes of direct timing driven placement after a first pass of non-direct timing driven placement. First, a high level description of the circuit design may be synthesized. Next, a non-direct timing driven placement process may place the design. Then the placed design may be routed. After routing, a modified design may be resynthesized. The resynthesized design may then be placed according to a direct timing driven placement process. This sequence may be repeated several times.
Another embodiment of the present invention allows for congestion driven routing through multiple loops of synthesis, direct timing driven placement and routing.
In one embodiment of the present invention, direct timing driven placement is made more useful by initializing the placer with non-direct timing driven placement.